相信迴文（palindrome）一定是在剛入門學習程式時一定會遇到的問題，
他雖然看起來很簡單，但的確可以教我們很多演算法上的思維。
本篇會提供三種解法，一起來看從暴力法到優雅的解題的過程吧！

迴文（palindrome）就是由前往後和由後往前念都像同的句子，像是'abcdcba'、'口罩罩口'...等等。

初學者一定有做過的方式，超直覺暴力法：

時間複雜度 : Ｏ(N^2) ，空間複雜度：Ｏ(N)

利用題目給你的字串反過來寫一次，也就是先建一個空字串，把字一個個加(concat)上去，這個步驟其實會造成Ｏ(N^2)的時間複雜度，而後我們又要把建立好的結果和原本的字串來做比對

程式碼會長得像下方⇊

function isPalindrome(string) {
  let reverseString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString += string[i];
  }
  return string === reverseString;
}

當然我們不能在這裡就放過這一題，再想想有沒有更好的做法？

如果一開始我們不建立一個空字串，建立一個空的陣列，我們用push的方式把加到array 相較一開的方式，這樣只花Ｏ(N)

然後把新建的array.join()的方式變成字串和原本相比

function isPalindrome(string) {
  const reverseString = [];
  for (let i = string.length - 1; i >= 0; i--) {
    reverseString.push(string[i]);
  }
  return string === reverseString.join('');
}

那有沒有辦法用遞迴（Recursion）的方式解決呢？

利用 return first === last and isPalindrome(middle)

但是Recursion的方式不一定有辦法減少space

因為tail recursion依舊需要用到stack

程式碼如下

function isPalindrome(string, i = 0) {
  const j = string.length - 1 - i;
  return i >= j ? true : string[i] === string[j] && isPalindrome(string, i + 1);
}

那有沒有辦法減少空間複雜度？

當然可以！好用的pointer又派上用場了！

來看pointer的解法！

function isPalindrome(string) {
  let start = 0;
  let end = string.length - 1;
  while (start < end) {
    if (string[start] !== string[end]) return false;
    start++;
    end--;
  }
  return true;
}

看完這寫方式，Leetcode的題目指示加上一些變化，我們可以利用正則表達式

有關正則表達式，這裡提供最近保哥線上提供的最新影片直播連接fb，有需要的可以再去觀看！

下面提供解答參考拉！

var isPalindrome = function(s) {
  s = s.replace(/[^0-9a-zA-Z]+/gim, '');
  s = s.toLowerCase();
  let start = 0;
  let end = s.length - 1;
  while (start < end) {
    if (s[start] !== s[end]) return false;
    start++;
    end--;
  }
  return true;
};

明日題目預告：
摸過簡單的Palindrome，當然要來看進階一點的題目！Longest Palindromic Substring